package com.formula.datastructure.exam.sort;

import com.formula.datastructure.util.DataUtil;

public class HeapSort {
    public Integer[] sort(Integer[] array) {
        int N = array.length;

        for (int i = N / 2; i >= 0; i--) {
            siftDown(array, i, N);
        }

        Integer temp;
        for (int i = N - 1; i > 0; i--) {
            temp = array[i];
            array[i] = array[0];
            array[0] = temp;
            siftDown(array, 0, i - 1);
        }

        return array;
    }

    void siftDown(Integer[] array, int idx, int len) {
        Integer temp;
        while (getLeft(idx) < len) {
            int i = getLeft(idx);
            if (i + 1 < len && array[i + 1] > array[i]) {
                i = i + 1;
            }
            if (array[i] > array[idx]) {
                temp = array[i];
                array[i] = array[idx];
                array[idx] = temp;
                idx = i;
            } else {
                break;
            }
        }
    }

    private int getLeft(int idx) {
        return 2 * idx + 1;
    }


    public static void main(String[] args) {
        HeapSort heap = new HeapSort();

        int size = 20;
        int range = 999;
        Integer[] array = DataUtil.genUniqueArray(size, range);
        DataUtil.printIndex(size);
        DataUtil.printArray(array);
        DataUtil.printArray(heap.sort(array));
    }

}
